package com.smh;

import org.junit.jupiter.api.Test;

/**
 * @author shiminghui
 * @date 2025/3/19 19:34
 * @description: TODO
 */
public class _067_快速幂 {


    @Test
    public void test1() {
        System.out.println(pow(2, Integer.MIN_VALUE));
    }

    /**
     * 利用分治的思想实现快速幂
     */
    public double pow(double x, long n) {
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return x;
        }
        if (n < 0) {
            x = 1.0 / x;
            n = -n;
        }

        if ((n & 1) == 0) {
            double temp = pow(x, n / 2);
            return temp * temp;
        } else {
            double temp = pow(x, n / 2);
            return temp * temp * x;
        }
    }


    /**
     * 求x的平方根的整数部分
     * 每次从1的平方开始寻找太好费时间了,我们可以用二分查找来优化
     */

    @Test
    public void test2() {
        System.out.println(mySqrt(2147483647));
    }

    public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        int max = (int) Math.sqrt((double) Integer.MAX_VALUE);
        int medium = 0;
        int left = 0;
        int right = x;
        while (left < right) {
            medium = (left + right) >>> 1; // mid = (left+right)/2;
            if (medium > max) {
                right = medium - 1;
                continue;
            }
            int temp = medium * medium; // 这里也可以用x/medium;来判断
            if (temp == x) {
                return medium;
            } else if (temp > x) {
                right = medium - 1;
            } else {
                left = medium + 1;
            }
        }
        if (left * left > x) {
            return left - 1;
        } else {
            return left;
        }
    }


}
